1. Field of the Invention
This invention pertains generally to image and video coding, and more particularly to an adaptive entropy coding apparatus and method utilizing set partitioning in generalized hierarchical trees.
2. Description of Related Art
Entropy coding is an important constituent of image and video compression, which is usually in response to the steps of (1) performing a transform (or optionally prediction prior to the transform), (2) quantization, and (3) entropy coding.
The following is described for the common JPEG entropy coding method, which stands for Joint Photographic Experts Group and is an ISO/IEC standard for a suite of computer image file compression techniques. A JPEG file is created by choosing from a range of compression qualities, or more accurately, from one of a number of compression algorithms. In converting an image through JPEG compression the target size or quality of the resultant image is specified to a quality level that approximates or is less than the original image. As the highest quality images result in the largest file, a trade-off is made between image quality and file size. The JPEG scheme according to the standard includes twenty-nine (29) distinct coding processes although a JPEG implementer may not use them all.
When performing entropy coding in JPEG, each 8×8 block is transformed using discrete cosine transforms (DCT), and the DCT coefficients are quantized, zig-zag scanned, and run-length coded. It will be recognized that run-length coding provides a way of encoding DCT coefficients at lower rates by creating linear groups of identical pixels rather than storing the values of each pixel individually. DCT provides a mechanism for expressing any waveform as a weighted sum of cosines, and it is central to numerous forms of signal processing, in particular that of image and video compression.
FIG. 1A illustrates an example of zig-zag scanning in a 4×4 block, with coefficient locations shown in FIG. 1B. A number of drawbacks exist for performing JPEG's entropy encoding according to this zig-zag pattern. In particular, there is (1) a lack of rate control mechanisms, while the (2) zig-zag scanning destroys the 2-D dependencies of the DCT coefficients, and (3) the fixed zig-zag scanning is based on the statistics of a large set of image data, therefore is not adaptive to the local characteristics (e.g., directionality) of the local image block.
It should be understood that the parameters used in quantization partially determine rate control, whereby different quantization parameters typically have to be tried to attain the desired file size.
Bit-plane based entropy coding is widely utilized in scalable image/video coding. In this process, transform coefficients are converted to the binary form, and coded from the most significant bit-plane (MSB) to the least significant bit-plane (LSB). During this process the encoding and decoding of lower bit-planes is based on a knowledge of higher bit-planes. The bitstream coding process can be stopped anywhere, toward satisfying a given bitrate budget while providing a reasonably good reconstruction quality. The ability to stop at any point in the coding process is possible since the most important part of each coefficient (MSBs) has been already coded. This bitstream coding mechanism is known as embedded coding and provides good rate control.
Regarding the loss of 2-D dependency, it will be seen for example, that coefficient locations 2 and 6 in FIG. 1B are close in frequency spectrum as shown in the 4×4 block, yet they are not adjacent and are actually far from one another in response to the zig-zag scanning order shown in FIG. 1A. For certain type of blocks, if coefficient location 2 is non-zero, there is a high probability that 6 is non-zeros as well; in this case, the zig-zag scanning could potentially interrupt a long run and decrease the coding efficiency.
To improve the coding efficiency of 2D visual signals such as images and videos, adaptation to local geometric features is a recent trend. However, these methods have not been well associated to suitable entropy coding methods, whereby statistical redundancy is not fully exploited. By contrast, the present invention, illustrates the importance of designing adaptive entropy coding methods.
Accordingly, a need exists for a method and apparatus for performing rate controllable entropy encoding and decoding which has low complexity and high efficiency. These needs and others are met within the present invention, which overcomes the deficiencies of previously developed entropy-based image/video coding techniques.